package com.linyaonan.leetcode.medium._1545;

/**
 * 给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：
 *
 * S1 = "0"
 * 当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
 * 其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。
 *
 * 例如，符合上述描述的序列的前 4 个字符串依次是：
 *
 * S1 = "0"
 * S2 = "011"
 * S3 = "0111001"
 * S4 = "011100110110001"
 * 请你返回  Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3, k = 1
 * 输出："0"
 * 解释：S3 为 "0111001"，其第 1 位为 "0" 。
 * 示例 2：
 *
 * 输入：n = 4, k = 11
 * 输出："1"
 * 解释：S4 为 "011100110110001"，其第 11 位为 "1" 。
 * 示例 3：
 *
 * 输入：n = 1, k = 1
 * 输出："0"
 * 示例 4：
 *
 * 输入：n = 2, k = 3
 * 输出："1"
 *  
 *
 * 提示：
 *
 * 1 <= n <= 20
 * 1 <= k <= 2n - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-kth-bit-in-nth-binary-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 首先很明显的规律是 Sn = (Sn-1) * 2 + 1
     * 并且如果index 如果等于 (Sn + 1) >> 1 那一定是1
     *      如果小于中间，则等于 Sn-1 的同index
     *      如果大于中间，则等于  Sn-1 的逆序且反转
     * @param n
     * @param k
     * @return
     */

    int[] Sn;

    /**
     * 取反次数
     */
    int fCount = 0;

    public char findKthBit(int n, int k) {
        fCount = 0;
        Sn = new int[n];
        Sn[0] = 1;

        for (int i = 1; i < n; i++) {
            Sn[i] = Sn[i - 1] * 2 + 1;
        }

        int i = find(n, k);
        return (char) (i + '0');
    }

    public int find(int n, int k) {
        if (n == 1) {
            return 0;
        }
        int mid = (Sn[n - 1] + 1) >> 1;

        if (mid == k) {
            return 1;
        }

        if (mid > k) {
            return find(n - 1, k);
        } else {
            fCount++;
            int i = find(n - 1, Sn[n - 1] - k + 1);
            if ((fCount & 1) == 1) {
                return i == 1 ? 0 : 1;
            } else {
                return i;
            }
        }
    }


}